---
title: "5、接龙序列"
created: 2025-11-28
tags:
  - 算法
---

# 5、接龙序列

## 题目 [接龙序列](https://www.lanqiao.cn/paper/3818/problem/3512/)

![[image-7ac8239d.png]]

## 思路分析

![[image-652939cd.png]]

这种朴素做法可以过一半数据 拿到7分

考试时可能优化不出 因为都用dp写了 哪还会去想优化 所以就这样了

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int first[N],last[N];

int f[N];

int n;

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++){

		string s;cin>>s;

		first[i]=s[0]-'0';

		last[i]=s.back()-'0';

	}

//	for(int i=1;i<=n;i++) cout<<first[i]<<" "<<last[i]<<endl;

	int res=0;

	for(int i=1;i<=n;i++){

		f[i]=1;

		for(int j=1;j<i;j++){

			if(last[j]==first[i]){

				f[i]=max(f[i],f[j]+1);

			}

		}

		res=max(res,f[i]);

	}

	cout<<n-res;

	return 0;

}
```

用g[10];存储第i个数字之前以末尾数字k(0 <= k <= 9)为结尾的接龙序列的max 即g[k]表示在第i个数字以前,为k为末尾的接龙序列的最大长度

那么就可以省去一层循环

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int f[N];

int first[N],last[N];

int g[N];//g[k]表示在第i个数字以前,为k为末尾的接龙序列的最大长度

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        string x;

        cin>>x;

        first[i]=x[0]-'0';

        last[i]=x.back()-'0';

    }

    int res=0;

    for(int i=1;i<=n;i++){

        f[i]=1;

        f[i]=max(f[i],g[first[i]]+1);//只关心以first[i]为结尾的数字

        g[last[i]]=max(g[last[i]],f[i]);//第i个数字的末尾为last[i],更新g[]

        res=max(res,f[i]);

    }

    cout<<n-res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/历年真题 模考特训/第十四届 c++ B组 省赛/4、飞机降落|4、飞机降落]] 🏠 [[00-刷题理模型]] ➡️ [[6、岛屿个数|6、岛屿个数]]